package lc.排序;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @description: 最小的k个数
 * @author: qian
 * @createDate: 2021/8/20
 */
public class 剑指Offer40_最小的k个数 {

    public int[] getLeastNumbers(int[] arr, int k) {
        // lc.优先队列
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1 );
        for(int i = 0; i < k; i++) {
            queue.add(arr[i]);
        }
        for(int i = k; i < arr.length; i++) {
            if (!queue.isEmpty() && queue.peek() > arr[i]) {
                queue.remove();
                queue.add(arr[i]);
            }
        }
        int []res = new int[k];
        for(int i = 0; i < k; i++) {
            res[i] = queue.remove();
        }
        return res;

    }
    // 快排
    public int[] getLeastNumber(int[] arr, int k) {
        if (k >= arr.length) return arr;
        return quickSort(arr,k,0,arr.length - 1);
    }

    private int[] quickSort(int[] arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            // 必须先和最后的数比较
            //while (i < j && arr[i] <= arr[l]) i++; 写前面会报错
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;

            swap(arr,i,j);
        }
        swap(arr,l,i);
        if (i > k) return quickSort(arr,k,l,i - 1);
        if (i < k) return quickSort(arr,k,i + 1,r);
        return Arrays.copyOf(arr,k);
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
